package main;

import java.util.LinkedList;
import java.util.Queue;

public class FindBottomLeftValue {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode left1 = new TreeNode(4);
        TreeNode right1 = new TreeNode(2);
        root.left = left1;
        root.right = right1;
        left1.left = new TreeNode(5);
        left1.right = new TreeNode(1);
        right1.right = new TreeNode(9);
        System.out.println(new FindBottomLeftValue().findBottomLeftValue(root));
    }
    public int findBottomLeftValue(TreeNode root){
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue1.offer(root);
        int bottomLeft = root.val;
        while (!queue1.isEmpty()){
            TreeNode node = queue1.poll();
            if (node.left != null){
                queue2.offer(node.left);
            }
            if (node.right != null){
                queue1.offer(node.right);
            }
            if (queue1.isEmpty()){
                queue1 = queue2;
                queue2 = new LinkedList<>();
                if (!queue1.isEmpty()){
                    bottomLeft = queue1.peek().val;
                }
            }
        }
        return bottomLeft;
    }

}
